#include <iostream>
#include <cassert>
using namespace std;
template <class T>
class List {
	struct ListNode {
		T data;
		ListNode* pre;
		ListNode* next;
	};
private:
	ListNode* m_list;
	int m_size;
public:
	List() {
		m_list = new ListNode;
		m_list->pre = m_list;
		m_list->next = m_list;
		m_size = 0;
	}
	List(T data) : List() {
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list;
		node->pre = m_list;
		m_list->next = node;
		m_list->pre = node;
		m_size++;
	}
	~List() {
		ListNode* it = m_list->next;
		ListNode* pr = nullptr;
		while (it != m_list) {
			pr = it;
			it = it->next;
			delete pr;
		}
		delete it;
		m_size = -1;
	}
public:
	void push_back(T data) {
		ListNode* node = new ListNode;
		node->data = data;
		m_list->pre->next = node;
		node->pre = m_list->pre;
		m_list->pre = node;
		node->next = m_list;
		m_size++;
	}
	void pop_back() {
		if (empty()) return;
		ListNode* current = m_list->pre;
		current->pre->next = m_list;
		m_list->pre = current->pre;
		delete current;
		m_size--;
	}
	void push_front(T data) {
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list->next;
		node->pre = m_list;
		node->next->pre = node;
		m_list->next = node;
		m_size++;
	}
	void pop_front() {
		if (empty()) return;
		ListNode* current = m_list->next;
		current->next->pre = m_list;
		m_list->next = current->next;
		delete current;
		m_size--;
	}
	void insert(int pos, T data) {
		assert(pos >= 0 && pos <= m_size);
		ListNode* node = new ListNode;
		node->data = data;
		ListNode* current = m_list;
		for (int i = 0; i < pos; ++i) {
			current = current->next;
		}
		node->pre = current;
		node->next = current->next;
		node->next->pre = node;
		current->next = node;
		m_size++;
	}
	void erase(T data) {
		ListNode* current = m_list->next;
		while (current != m_list) {
			if (current->data == data) {
				current->pre->next = current->next;
				current->next->pre = current->pre;
				delete current;
				m_size--;
				return;
			}
			current = current->next;
		}
	}
	void eraseAll(T data) {
		ListNode* current = m_list->next;
		ListNode* del = nullptr;
		while (current != m_list) {
			if (current->data == data) {
				current->pre->next = current->next;
				current->next->pre = current->pre;
				del = current;
				current = current->next;
				delete del;
				m_size--;
			}
			else {
				current = current->next;
			}
		}
	}
	void clear() {
		ListNode* it = m_list->next;
		ListNode* pr = nullptr;
		while (it != m_list) {
			pr = it;
			it = it->next;
			delete pr;
		}
		it->pre = it;
		it->next = it;
		m_size = 0;
	}
	int find(T data) {
		ListNode* current = m_list->next;
		for (int i = 0; current != m_list; ++i) {
			if (current->data == data) return i;
			current = current->next;
		}
		return -1;
	}
public:
	bool empty() {
		return m_list->next == m_list;
	}
	int size() {
		return m_size;
	}
	T& operator[](int index) {
		assert(index < m_size && index >= 0);
		ListNode* current = m_list->next;
		while (index--) {
			current = current->next;
		}
		return current->data;
	}
};
int main() {
	List<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);
	list.insert(5, 3);
	list.eraseAll(3);
	for (int i = 0; i < list.size(); ++i) {
		cout << list[i] << " ";
	}
	cout << endl;
	return 0;
}